<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>队列封装</title>
</head>
<body>
    
</body>
</html>
<script>
    // 基于数组封装队列，该方法性能不高
    function Queue(){
        this.list = []

        Queue.prototype.enqueue = function(params){
            this.list.push(params)
        }

        Queue.prototype.dequeue = function(){
            return this.list.shift()
        }
        Queue.prototype.front = function(){
            return this.list[0]
        }
        Queue.prototype.size =function(){
            return this.list.length
        }
        Queue.prototype.isEmpty = function(){
            return this.list.length === 0
        }
        Queue.prototype.toString = function(){
            let s = ''
            for(var i = 0; i < this.list.length; i++){
                s += this.list[i] + ' '
            }
            return s
        }
    }

    // 算法面试题（击鼓传花）
    // 几个朋友玩一个游戏，围成一个圈，开始数数，数到某个数字时，对应位置的人淘汰
    // 直到只剩一个人时游戏结束，并求出剩余的那一个人原来的位置
    // nameList为玩游戏的人组成的数组， num为数到的数字
    /* 
       思路：利用队列求解
       1、num之前的人不会被淘汰，放入队列最后面
       2、删除num位置的元素
       3、从新开始数数，重复1、2步骤，直到队列中仅剩一人
    */
    function DrummingToPassFlowers(nameList, num) {
        // 1、创建队列
        var queue = new Queue();
        // 2、将数组nameList中的元素添加进队列中
        nameList.forEach(item => {
           queue.enqueue(item)
        })
        alert(queue)
        // 5、重复执行3、4，直到队列中只剩一人
        while(queue.size() > 1){
           // 3、将num之前的元素添加到队列末尾
           for(var i = 0; i < num-1; i++){
               alert(queue.front())
               queue.enqueue(queue.dequeue())
               alert(queue.front())
               alert(queue)
           }
           // 4、删除num位置的元素
           queue.dequeue()
           alert(queue)
        }
        // alert(queue)
        var endName = queue.front()
        return nameList.indexOf(endName)
    }

    var na = ['qoqo', 'wowo', 'eoeo', 'roro', 'toto', 'yoyo']

    alert(DrummingToPassFlowers(na, 4));
</script>